/**
 *  Copyright (C) 2013  Piotr Szczepański
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
package edu.pw.elka.gtsna.community_detection;


import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Vector;

import edu.pw.elka.gtsna.graph.Graph;

/**
 * @author Piotr Lech Szczepański
 * @author P.Szczepanski@ii.pw.edu.pl 
 *
 */
public class GreedyModularity extends AbstractCommunityDetection {

	//For general dataset storage
	public Hashtable<Integer,Hashtable<Integer,Double>> neighbours;

	//For InfMax model
	private Vector<Integer> S;
	private double reach_S;
	public Hashtable<Integer,Double> init_thresholds;
	private int iterations;
	private int K;
	
	
	public GreedyModularity(Graph graph,  int iterations, int K) {
		super(graph);
		this.init_thresholds=new Hashtable<Integer,Double>();
		this.iterations=iterations;
		this.K=K;
		neighbours = new Hashtable<Integer,Hashtable<Integer,Double>> ();
		for (int v: graph.getAllNodes()) {
			neighbours.put(v, new Hashtable<Integer,Double>());
		}
		
		ReadTabSep();
		System.out.println("Graph read");
		Choose_K();		

	}
	
	
	/* (non-Javadoc)
	 * @see edu.pw.elka.gtsna.community_detection.CommunityStructureDetectable#detectCommunities()
	 */
	@Override
	public CommunityStructure detectCommunities() {
		// TODO Auto-generated method stub
		return null;
	}
	
	private void ReadTabSep() {

			double wt = 1.0;
			for (int v: graph.getAllNodes()) {
				for (int neighbour: graph.getNeigbours(v)) {
					neighbours.get(v).put(neighbour, wt);
					neighbours.get(neighbour).put(v, wt);
				}
			}		

	}
	
	private void Choose_K() {
		this.S=new Vector<Integer>();
		this.reach_S=0;
		int K=this.K;
		int k=0;

		Hashtable<Integer,Double> mc_arr = new Hashtable<Integer,Double>();
		
		for(int node : graph.getAllNodes()) {
			mc_arr.put(node, 0.0);
		}
		
		int r=0;
		for(r=0;r<this.iterations;r++) {
			System.out.println("Iteration: "+r+"/"+iterations);
			
			RandomizeThresholds();
			
			for(int node : graph.getAllNodes()) {
				Hashtable<Integer,Double> curr_thresholds = (Hashtable<Integer, Double>) init_thresholds.clone();
				if(!S.contains(node))
				{
					Vector<Integer> candidate_S=(Vector<Integer>)S.clone();
					candidate_S.add(node);
					double reach_candidate_S=LT_Model(candidate_S,curr_thresholds);
					double marg_contrib=reach_candidate_S-reach_S;
					mc_arr.put(node, mc_arr.get(node) + marg_contrib);
				}
			}
		}

		
	   LinkedHashMap<Integer, String[]> arr_to_sort = new LinkedHashMap<Integer, String[]>();
		
		for(int node : graph.getAllNodes()) {
			arr_to_sort.put(node, new String[2]);
			arr_to_sort.get(node)[0]=String.valueOf(mc_arr.get(node)/iterations);
			arr_to_sort.get(node)[1]=String.valueOf(node);
		}
	   

       //Transfer as List and sort it
       ArrayList<Map.Entry<?, String[]>> l = new ArrayList(arr_to_sort.entrySet());
       Collections.sort(l, new Comparator<Map.Entry<?, String[]>>(){

         public int compare(Map.Entry<?, String[]> o1, Map.Entry<?, String[]> o2) {
				final double time1 = Double.parseDouble(o1.getValue()[0]);
				final double time2 = Double.parseDouble(o1.getValue()[0]);
				return Double.compare(time1, time2);
        }});


		Vector<Double> mc_values=new Vector<Double>();
		Vector<Integer> index_int=new Vector<Integer>();

		for(int i=l.size() -1;i>=0;i--) {
			mc_values.add(Double.parseDouble(l.get(i).getValue()[0]));
			index_int.add(Integer.parseInt(l.get(i).getValue()[1]));
		}

		Get_K(K,mc_values,index_int,r);
	}
	
	private void RandomizeThresholds()
	{		
		for(int node : graph.getAllNodes()) {
			double temp=Math.random();
			init_thresholds.put(node, temp);
		}
	}
	
	public void Get_K(int K, Vector<Double> mc_values, Vector<Integer> index_int, int iters) {
		int k=0;
		System.out.println(mc_values);
		double reach_S=0;

		int node_with_max=index_int.elementAt(0);
		double max_value=mc_values.elementAt(0);

		S.add(node_with_max);
		reach_S=reach_S+(double)max_value;

		System.out.println("Reach of S="+reach_S);
		index_int.remove(0);
		mc_values.remove(0);

		k++;

		System.out.println(S);
		System.out.println("Node "+node_with_max+" with MC="+max_value+" Added");

		while(k<K) {
			int candidate_node=index_int.elementAt(0);
			double candidate_mc_val=mc_values.elementAt(0);

			Vector<Integer> candidate_S=(Vector<Integer>)S.clone();
			candidate_S.add(candidate_node);

			double sum_reach=0;
			
			for(int r=0;r<iters;r++)
			{
				this.RandomizeThresholds();
				double reach_candidate_S=LT_Model(candidate_S,init_thresholds);
				double marg_contrib=reach_candidate_S-reach_S;
				sum_reach=sum_reach+marg_contrib;
			}

			mc_values.set(0,sum_reach/iters);
			candidate_mc_val=sum_reach/iters;

			if(candidate_mc_val>mc_values.elementAt(1))
			{
				S.add(candidate_node);
				reach_S=reach_S+(double)candidate_mc_val;

				index_int.remove(0);
				mc_values.remove(0);

				k++;

				

				System.out.println(S.lastElement()+"\t"+reach_S+"\n");
				
				System.out.println(S);
				System.out.println(k+","+reach_S);



			}
			else
			{
				int i=0;
				while(i+1<mc_values.size() && mc_values.elementAt(i)<mc_values.elementAt(i+1))
				{
					double temp_mc_val=mc_values.elementAt(i);
					int temp_index=index_int.elementAt(i);

					mc_values.set(i,mc_values.elementAt(i+1));
					mc_values.set(i+1,temp_mc_val);

					index_int.set(i,index_int.elementAt(i+1));
					index_int.set(i+1,temp_index);

					i++;
				}
			}
		}
		System.out.println("S="+S);

	}

	private double LT_Model(Vector<Integer> active_nodes, Hashtable<Integer,Double>  thresholds) {
		Vector<Integer> reach_V=new Vector<Integer>();	//all the nodes initial node made active
		Queue<Integer> got_activated=new LinkedList<Integer>();	//The Queue maintaining how each node is getting activated
		
		for(int i=0;i<active_nodes.size();i++)
		{
			int node_add=active_nodes.elementAt(i);
			got_activated.add(node_add);
			reach_V.add(node_add);
		}

		while(!got_activated.isEmpty())
		{
			int node=got_activated.poll();
			Enumeration nog=neighbours.get(node).keys();

			while(nog.hasMoreElements())
			{
				int dest=(Integer)nog.nextElement();

				if(!reach_V.contains(dest))
				{
					double active_sum=neighbours.get(dest).get(node);
					double sum= graph.getDegree(dest);				
					double temp=(double)(active_sum/sum);
					
					if(temp>thresholds.get(dest))
					{
						if(!reach_V.contains(dest) && !got_activated.contains(dest))
						{
							reach_V.add(dest);
							got_activated.add(dest);
						}
					}
					else
					{
						thresholds.put(dest, thresholds.get(dest)-temp);
					}
				}
			}
		}
		return (reach_V.size());
	}
	
}
